function ListNode(val, next) {
  this.val = val === undefined ? 0 : val;
  this.next = next === undefined ? null : next;
}

let list = new ListNode(1)
list.next = new ListNode(2)
list.next.next = new ListNode(3)
list.next.next.next = new ListNode(4)
list.next.next.next.next = new ListNode(5)

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
const removeNthFromEnd1 = function (head, n) {
  let nodeList = [head],
    temp = head;
  // 因为节点数量小于30，将所有节点保存在数组中。也可以先循环出来链表的长度，再处理
  while (temp.next) {
    nodeList.push(temp.next);
    temp = temp.next;
  }
  // 特殊情况处理：链表长度为1且删除
  if (nodeList.length === 1 && n === 1) return null;
  if (nodeList.length === n) {
    // 特殊情况处理：删除头节点
    head = head.next;
  } else {
    nodeList[nodeList.length - n - 1].next = nodeList[nodeList.length - n - 1].next.next;
  }
  return head;
};



/**
 * 双指针
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
const removeNthFromEnd2 = function (head, n) {
    // 添加一个哑结点，代替头结点的判断
    let dummyNode = new ListNode(0, head)
    let first = head, second = dummyNode
    // first从head开始往后循环至链表长度次
    while (n--) {
        first = first.next
    }
    while (first) {
        first = first.next
        // secode循环剩下次数，因为加了一个哑结点，所以正好到需要删除节点的前一个节点
        second = second.next
    }
    second.next = second.next.next
    dummyNode = dummyNode.next
    return dummyNode
};